//
// Created by lm379 on 25-3-11.
//
#include <iostream>
using namespace std;

typedef struct LinkList {
    int data;
    LinkList * next;
} LinkList;

void CreateLinkList(const int arr[],LinkList *& head,int length) {
    head = static_cast<LinkList *>(malloc(sizeof(LinkList)));
    head -> next = nullptr;
    LinkList *p = head;
    LinkList *q = nullptr;
    for (int i = 0; i < length; i++) {
        q = static_cast<LinkList *>(malloc(sizeof(LinkList)));
        q -> data = arr[i];
        q -> next = nullptr;
        p -> next = q;
        p = q;
    }
}

// 循环实现
void merge(const int a[], const int b[], const int an, const int bn, int c[]) {
    int i = 0, j = 0, k = 0;
    while (i<an && j < bn) {
        if (a[i] < b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i<an) {
        c[k++] = a[i++];
    }
    while (j<bn) {
        c[k++] = b[j++];
    }
}

// 归并链表--尾插法
void mergeLink(LinkList *a,LinkList *b,LinkList *&c) {
    LinkList *p = a -> next;
    LinkList *q = b -> next;
    LinkList *r = nullptr;
    c = a;
    c -> next = nullptr;
    free(b);
    r = c;
    while (p != nullptr && q != nullptr) {
        if (p -> data< q -> data) {
            r -> next = p;
            p = p->next;
        } else {
            r -> next = q;
            q = q -> next;
        }
        r = r -> next;
    }
    if (p != nullptr)
        r -> next = p;
    if (q != nullptr)
        r -> next = q;
}

void PrintList(const LinkList *L) {
    const LinkList *p = L -> next;
    while (p != nullptr) {
        cout << p -> data << " ";
        p = p -> next;
    }
    cout << endl;
}

int main() {
    constexpr int a[] = {0,2,7,9};
    const int b[] = {1,4,8,11,12,13,14};
    constexpr int an = size(a);
    constexpr int bn = size(b);
    LinkList *linka;
    LinkList *linkb;
    CreateLinkList(a,linka,an);
    CreateLinkList(b,linkb,bn);
    mergeLink(linka,linkb,linka);
    cout << "Link Merge:\n";
    PrintList(linka);
    int c[an+bn];
    merge(a,b,an,bn,c);
    cout << "Arr Merge:\n";
    for (int i = 0; i < an + bn ; i++) {
        cout << c[i] << " ";
    }
    cout << endl;
    return 0;
}